package com.leetcode.二叉树.广度优先;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
 * @author LZF
 *
 */
public class L107二叉树的层序遍历II {
	//利用迭代实现层次遍历(见L102)，再将最后的结果集反转一下即可。
	public List<List<Integer>> levelOrderBottom(TreeNode root) {
		List<List<Integer>> resList = new ArrayList<>();
		Queue<TreeNode> que = new LinkedList<>();
		if(root != null) que.offer(root);
		while(!que.isEmpty()) {
			int len = que.size();
			List<Integer> result = new ArrayList<Integer>();
			while(len > 0) {
				TreeNode node = que.poll();
				result.add(node.val);
				if(node.left != null) que.offer(node.left);
				if(node.right != null) que.offer(node.right);
				len--;
			}
			resList.add(result);
		}
		Collections.reverse(resList);//结果反转
		return resList;
    }
	
	//树的定义
	class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode() {
		}

		TreeNode(int val) {
			this.val = val;
		}

		TreeNode(int val, TreeNode left, TreeNode right) {
			this.val = val;
			this.left = left;
			this.right = right;
		}
	}
}